package primary.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Elephas
 * @Date 2022/1/10
 **/
public class IsSymmetric {
    public static void main(String[] args) {
        final TreeNode TEST01 = TreeNode.buildTreeNode(new Integer[]{1,2,2,null,3,null,3});
        final TreeNode TEST02 = TreeNode.buildTreeNode(new Integer[]{6,82,82,null,53,53,null,-58,null,null,-58,null,-85,-85,null,-9,null,null,-9,null,48,48,null,33,null,null,33,81,null,null,81,5,null,null,5,61,null,null,61,null,9,9,null,91,null,null,91,72,7,7,72,89,null,94,null,null,94,null,89,-27,null,-30,36,36,-30,null,-27,50,36,null,-80,34,null,null,34,-80,null,36,50,18,null,null,91,77,null,null,95,95,null,null,77,91,null,null,18,-19,65,null,94,null,-53,null,-29,-29,null,-53,null,94,null,65,-19,-62,-15,-35,null,null,-19,43,null,-21,null,null,-21,null,43,-19,null,null,-35,-15,-62,86,null,null,-70,null,19,null,55,-79,null,null,-96,-96,null,null,-79,55,null,19,null,-70,null,null,86,49,null,25,null,-19,null,null,8,30,null,82,-47,-47,82,null,30,8,null,null,-19,null,25,null,49});
        isSymmetric(TEST02);
    }

    /*
        解法一：层序遍历，检查每一层是否对称
     */
    public static boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        int levelNums = 1;
        while(!queue.isEmpty()){
            List<Integer> integerList = new ArrayList<>();
            boolean isEmpty = true;
            for (int i = 0; i < levelNums; i++) {
                TreeNode temp = queue.remove();
                if(temp != null){
                    integerList.add(temp.val);
                    isEmpty = false;
                    queue.add(temp.left);
                    queue.add(temp.right);
                }else{
                    queue.add(null);
                    queue.add(null);
                    integerList.add(null);
                }
            }
            for (int i = 0; i < levelNums/2; i++) {
                if(integerList.get(i) != integerList.get(levelNums - i -1)){
                    return false;
                }
            }
            if(isEmpty)
                break;
            levelNums = levelNums << 1;
        }
        return true;
    }
}
